0779. 第K个语法符号【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 递归

1. 📝 题目描述

• leetcode

我们构建了一个包含 n 行( 索引从 1 开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

• 例如，对于 n = 3，第 1 行是 0，第 2 行是 01，第 3 行是 0110。

给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

---

示例 1：

输入: n = 1, k = 1
输出: 0
解释: 第一行：0

示例 2：

输入: n = 2, k = 1
输出: 0
解释:
第一行: 0
第二行: 01

示例 3：

输入: n = 2, k = 2
输出: 1
解释:
第一行: 0
第二行: 01

---

提示：

• 1 <= n <= 30
• 1 <= k <= 2^n - 1

2. 🎯 s.1 - 递归

c

int kthGrammar(int n, int k) {
    if (n == 1) return 0;
    if (k % 2 == 1) return kthGrammar(n - 1, (k + 1) / 2);
    return 1 - kthGrammar(n - 1, k / 2);
}

js

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kthGrammar = function (n, k) {
  if (n === 1) return 0
  if (k % 2 === 1) return kthGrammar(n - 1, Math.ceil(k / 2))
  return 1 - kthGrammar(n - 1, k / 2)
}

py

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0
        if k % 2 == 1:
            return self.kthGrammar(n - 1, (k + 1) // 2)
        return 1 - self.kthGrammar(n - 1, k // 2)

• 时间复杂度：$O(n)$，递归深度为 n
• 空间复杂度：$O(n)$，递归栈空间

算法思路：

• 第 n 行第 k 个元素由第 n-1 行第 ⌈k/2⌉ 个元素生成
• 若 k 为奇数，则结果与父节点相同；若 k 为偶数，则结果为父节点取反